package com.mj.listen2._02_并查集.generic;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 自定义类型使用并查集
 *
 * @param <V>
 */
public class GenericUnionFind<V> {

    // 并查集使用map来存储  key:元素，value:元素对应的节点信息
    private Map<V, Node<V>> map = new HashMap<>();

    public void makeSet(V v) {
        if (map.containsKey(v)) return;
        map.put(v, new Node<>(v));
    }

    /**
     * 找出V对应的根节点
     *
     * @return
     */
    private Node<V> findNode(V v) {
        // 直接从map中取出，因为之前应该存储过了
        Node<V> node = map.get(v);
        if (node == null) return null;
        // 遍历超出根节点
        // 让当前v直接指向对应的祖父节点
        while (!Objects.equals(node.value, node.parent.value)) {
            // 让当前v的父节点为祖父节点
            node.parent = node.parent.parent;
            // 最新的parents[v]再继续往上循环迭代
            node = node.parent;
        }
        return node;
    }

    /**
     * 查找元素V的根节点所对应的值(PS:需要先找到节点，再取节点对应的值)
     *
     * @param v
     * @return
     */
    public V find(V v) {
        Node<V> node = findNode(v);
        return node == null ? null : node.value;
    }

    /**
     * 将v1合入v2。v1的根节点，改为v2的根节点
     *
     * @param v1
     * @param v2
     */
    public void union(V v1, V v2) {
        // 找到 v1/v2 所在的根节点
        Node<V> p1 = findNode(v1);
        Node<V> p2 = findNode(v2);
        if (p1 == null || p2 == null) return;

        // 本身v1和v2就是同一个集合
        if (Objects.equals(p1.value, p2.value)) ;

        // 比较rank
        if (p1.rank < p2.rank) {
            // p1根节点子树高度小于p2根节点子树的高度。让p1根节点改为p2
            p1.parent = p2;
        } else if (p1.rank > p2.rank) {
            // p2根节点子树高度小于p1根节点子树的高度。让p2根节点改为p1
            p2.parent = p1;
        } else {
            // 相同的话，谁改为谁都可以
            p1.parent = p2;
            p2.rank++;
        }
    }

    /**
     * 两个元素是都是同一个集
     *
     * @param v1
     * @param v2
     * @return
     */
    public boolean isSame(V v1, V v2) {
        // 判断两个值对应的根节点是否相同，相同才是同一个集
        return Objects.equals(find(v1), find(v2));
    }

    private static class Node<V> {
        // 每个节点的具体值(对象)
        V value;
        // 节点指针，指向parent。默认的parent都是指向自己
        Node<V> parent = this;
        // rank，根据高度决定怎么合并两个节点
        int rank = 1;

        public Node(V value) {
            this.value = value;
        }
    }
}
